using System;
using System.Linq;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0016. 最接近的三数之和")]
    public class No0016_ThreeSumClosest : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(ThreeSumClosest, new int[] { -1, 2, 1, -4 }, 1, 2);
        }

        public int ThreeSumClosest(int[] nums, int target)
        {
            nums = nums.OrderBy(i => i).ToArray();
            int n = nums.Length;
            int best = 10000000;

            for (int i = 0; i < n; i++)
            {
                int a = nums[i];
                if (i > 0 && nums[i] == nums[i - 1])
                {
                    continue;
                }

                int l = i + 1, r = n - 1;
                while (l < r)
                {
                    int b = nums[l];
                    int c = nums[r];
                    int sum = a + b + c;
                    if (sum == target)
                    {
                        return target;
                    }

                    if (Math.Abs(sum - target) < Math.Abs(best - target))
                    {
                        best = sum;
                    }

                    if (sum > target)
                    {
                        int r0 = r;
                        while (l < r0 && nums[r0] == nums[r])
                        {
                            r0--;
                        }
                        r = r0;
                    }
                    else
                    {
                        int l0 = l;
                        while (l0 < r && nums[l0] == nums[l])
                        {
                            l0++;
                        }
                        l = l0;
                    }
                }
            }
            return best;
        }
    }
}
